package com.gitee.feizns.explore.data_structure.linked_list.singly.middle;

/**
 * 链表的中间节点
 * 1 -> 2 -> 3          return 2
 * 1 -> 2 -> 3 -> 4     return 3
 * @author feizns
 * @since 2019/10/29
 */
public class Main {

    private static ListNode create() {
        ListNode ret = new ListNode(1);
        ret.next = new ListNode(2);
        ret.next.next = new ListNode(3);
        ret.next.next.next = new ListNode(4);
        ret.next.next.next.next = new ListNode(5);
        return ret;
    }

    public static void main(String[] args) {
        ListNode listNode = create();
        middleNode(listNode).print();
    }

    public static ListNode middleNode(ListNode head) {
        if ( head != null ) {
            ListNode slow = head;
            ListNode fast = head;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }

            return fast.next != null ? slow.next : slow;
        }
        return null;
    }

}
